# 추가 설명

2026년 8월 26일 알고리즘
추가 설명 — 되짚기는 길 하나가 아니라 영역을 준다
편집 거리의 표는 최솟값만 담는다. 표를 거꾸로 읽어 연산을 복원하면 최선의 길이 여럿일 수 있고, 그래서 결과는 길 하나가 아니라 표 위의 영역이 된다.
2026년 8월 6일 알고리즘
추가 설명 — 왜 이어 붙이는 것이 최선인가
최대 부분배열의 갱신식은 '앞부분의 최선은 kⱼ' 라는 한 줄을 당연하게 쓴다. 그 한 줄을 후보끼리의 1:1 대응으로 증명하고, 누적합에서 지금까지의 최소를 빼는 다른 풀이가 사실 같은 값을 계산한다는 것까지 보인다.
2026년 7월 31일 알고리즘
추가 설명 — 어떤 순서로 곱했는지 되짚기
동적 계획법 ③의 표는 최소 비용만 담는다. 어떤 괄호 순서로 곱해야 그 비용이 나오는지는 표에 없다. 채우는 동안 이긴 분할점 k를 함께 적어 두면 (1,n)에서 재귀로 (M₁(M₂M₃)) 같은 괄호화를 복원한다. d=[3,2,4,2] 예시로 되짚고, 파스 트리와 동점의 미묘함까지 짚는다.
2026년 7월 28일 알고리즘
추가 설명 — 어느 날을 골랐는지 되짚기
동적 계획법 ②의 표는 최댓값만 담는다. 채운 표를 마지막 칸부터 거꾸로 읽으면 어느 날을 골랐는지도 복원된다. a=[3,5,6,10] 예시로 직접 되짚고, 되짚기를 코드로 옮긴 뒤 동점 처리의 미묘함까지 짚는다.
2026년 7월 23일 알고리즘
추가 설명 — Strassen의 7은 어디서 왔고, 왜 최소인가
Strassen의 7개 곱은 어디서 왔을까. '곱셈 한 번'을 이중선형 곱으로 다시 보면 최소 곱셈 수는 그 사상의 랭크가 된다. 복소수 곱을 3번으로 줄이는 가우스의 요령을 발판 삼아 2×2 행렬 곱의 랭크가 정확히 7(6은 불가능)임을 보인다.
2026년 7월 15일 알고리즘
추가 설명 — 평행한 변이 만드는 동률과 대척점 쌍 열거
볼록 껍질 ⑤의 Rotating Calipers 뼈대는 평행한 변이 있어도 지름 값이 옳다. 이 글은 대척점 쌍 열거가 왜 별개 문제인지, 평행한 변이 만드는 동률과 교차 쌍을 어떻게 채우는지를 다룬다. 완전성(빠짐없음)은 얻되 유일성(중복 없음)은 얻지 못하며, 그 차이가 어디서 오는지까지 밝힌다.
2026년 7월 10일 알고리즘
추가 설명 — 균형 트리에서 접선을 O(log N)에 찾기
볼록 껍질 ③이 미뤄둔 부분. x좌표로 정렬된 볼록 사슬을 균형 트리에 담아, 외부 점에서 그은 접선의 접점을 O(log N)에 찾는 법. 후보 꼭짓점의 두 이웃 변에 CCW를 돌려 방향을 판정하고, 그것이 왜 이진 탐색이 되는지 따라간다.
2026년 7월 2일 알고리즘
추가 설명 — 균형 이진 탐색 트리는 어떻게 y로 정렬하고 구간을 찾는가
가장 가까운 점 쌍 ③에서 활성 집합을 떠받친 균형 BST(std::set)의 내부를 본다. 왜 정렬 배열·연결 리스트가 아닌 균형 BST인지, y를 키로 두면 왜 트리가 곧 y정렬인지, [y-D, y+D] 구간을 O(log n + 개수)에 찾는 원리를 짚는다.
2026년 6월 30일 알고리즘
추가 설명 — 왜 다음 7개만 비교하면 되는가
가장 가까운 점 쌍의 combine에서, 한 점이 옆에 있는 점을 몇 개만 비교해도 되는 이유를 쉽게 풀어 본다. 핵심은 '가까운 점은 좁은 공간에 빽빽이 들어갈 수 없다'는 것. 후보가 들어올 칸을 잘게 쪼개 세면, 비교 대상이 n과 무관한 상수(최대 7개)로 묶인다.
2026년 6월 29일 알고리즘
추가 설명 — 왜 하필 5개로 나누는가
median of medians가 그룹을 5개로 나누는 이유. 그룹 크기 g를 일반화해 두 부분문제 비율의 합이 1보다 작아야 선형임을 보인다. g=3과 g=4는 합이 정확히 1이라 깨지고, g=5는 0.9로 성립한다. g=7 이상은 수축이 좋아지는 대신 그룹 정렬 비용이 늘어 맞선다.
2026년 6월 29일 알고리즘
추가 설명 — quickselect는 왜 평균 O(n)인가
선택 문제 본문이 '대부분 O(n)'으로 넘어간 quickselect의 평균 시간을 기댓값 점화식으로 엄밀히 따진다. quick sort와 달리 한쪽으로만 재귀하기 때문에 E(n)에 max 항이 생기고, 이를 상계로 풀면 E(n) ≤ 4n = O(n)이다.